package 根据身高重建队列;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

/**
 * @author: AirMan
 * @date: 2025/4/24 14:39
 * @description:
 */
public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // greedy
        // 两个维度的问题：需要我们拆分维度进行考虑，一定要先确定一个维度，然后再去确定另一个维度，否则就会顾此失彼
        // 时先确定身高维度，还是确定数量维度呢？如果先确定数量维度，其实我们身高和数量两个维度都没确定下来
        // 所以我们要先确定身高维度，相同身高的，数量越小排越前面
        // 当确定身高维度之后，在确定数量维度。从大到小，数量时几就将该身高的人插入到指定位置！
        // 局部最优：在确定身高维度之后，优先按照身高最高的people的k进行插入，插入过后的people满足queue的属性
        // 全局最优：最后插入完成 ==> 整个queue都满足属性

        // 按照身高维度进行排序
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int height = o1[0] - o2[0];
                if (height > 0) {
                    return -1;
                } else if (height == 0) {
                    if (o1[1] > o2[1]) {
                        return 1;
                    } else {
                        return -1;
                    }
                } else {
                    return 1;
                }
            }
        });

        // 贪心算法：按照数量进行插入，每次都按照k进行插入 ==> 每个人都呆在了合适的k中
        LinkedList<int[]> queue = new LinkedList<>();
        for (int[] person : people) {
            // index: person[1]（数量）
            queue.add(person[1], person);
        }

        int[][] result = queue.toArray(new int[people.length][2]);

        return result;
    }
}
